COMP124

All notes > Week 10.2 Deadlock

Dining Philosophers Problem

In the producer-consumer problem

This problem helps visualise two common issues with concurrent systems:

There are N philosophers seated around a table

Solution Approach

Each philosopher has a unique index value in the set {0, 1, 2, 3, 4}
Each chopstick has an index from the set {0,1, 2, 3, 4}
The philosopher with index K must wait for both chopsticks K and (K+1)%5
When a philosopher eats, they block two other philosophers (their neighbours)

A problem here could be that one chopstick could be picked up by a philosopher before they pick up the other one, allowing the other one to be taken by another philosopher

Java Semaphore Solution

Treating each chopstick as a shared resource with its own critical region

class Chopstick {
	private volatile boolean using = false;
	public synchronized void pickUp() {
		while(using) {
			try { wait(); } catch(InterruptedException e) {}
		}
		using = true;
	}
	public synchronized void putDown() {
		using = false;
		notify();
	}
}

Each philosopher is a thread with a run() method

public void run() {
	while(alive) {
		think();
		stick[i].pickUp();          //            NON
		stick[(i+1)%%5].pickUp();   //      ATOMIC STATEMENTS
		eat();
		stick[i].putDown();
		stick[(i+1)%5].putDown();
	}
}

Each chopstick has a semaphore

Because of the non-atomic statements, you could get a race condition. If a thread is interrupted between when it picks up the first chopstick and when it picks up the second chopstick, you get a synchronisation issue.

Starvation

We can't guarantee

Without proper controls on when threads run, some philosophers could starve

In general, starvation occurs when one or more of the threads (or processes) in a concurrent system is denied access to the resources it needs

Deadlock

Suppose each philosopher picks up the chopstick to their right simultaneously

In general, deadlock occurs in a concurrent system when each thread (or process) is waiting for one of the others to do something (or release something)

Deadlock Solutions

Some rules could be added to the code to prevent deadlock

The dining philosophers problem helps us to understand the issues that can occur at the operating system level with processes and resources

Resource Allocation & Deadlock

The OS must allocate and share resources sensibly

In its simplest form, deadlock will occur in the following situation:

Deadlock Prevention

Processes could be forced to claim all resources in one atomic operation

Each resource could be numbered and processes could be forced to claim them in a specific order

Processes could be forced to use only one resource at a time

Resource Allocation Graphs

A graph can be drawn that models the processes and resources in a system

![[Pasted image 20250519082852.png]]
Arrow Directions

Suppose P3 requests access to R2

Deadlock Detection and Recovery

Resource allocation graph is monitored by the OS

If a cycle is detected, the OS could:

Each solution involves losing some processing time and even losing some data

Deadlock Avoidance

Deadlock avoidance is very similar to deadlock prevention

The banker's algorithm is a theoretical approach to deadlock avoidance

Ignoring Deadlock

It is practically impossible to implement efficient deadlock detection or prevention

The ostrich algorithm is a common approach in many modern systems

Windows and Linux ignore deadlock and don't do anything to detect or prevent it
The JVM also ignores deadlock when scheduling individual Java threads

Eg. when a program is unresponsive or you get a blue screen of death, this could be caused by deadlock since the OS does nothing to try to prevent it.